The present invention relates to an apparatus and a method for the processing of a plurality of tasks in a processor of a real-time data processing installation in which each task is to be processed individually by the processor according to a dynamically allocated priority and within a predetermined time period.
In a real-time system of the type named above having a dynamic priority allocation, the priority of a task or of an interrupt is assigned according to the relative urgency, in relation to the time at which a task is available for processing or an interrupt is requested.
In many of the previously used systems, a static priority allocation is used for tasks and interrupt requests that does not change over the course of time. In order to enable the timely processing of all tasks in such a system with n independent periodic tasks, the utilization of processor capacity may not exceed the theoretical value of n(2.sup.1/n -1). For large n, this value converges rapidly to ln2=0.69. That is, the utilization of processor capacity in such a system can be a maximum of only 70%, and the processor requires at least 30% idle time in order to be able to process all tasks in a timely fashion.
For the improvement of the utilization of the processor capacity, and thus of the performance of the data processing apparatus as a whole, the realization of a dynamic priority allocation has already been tried. A theoretical foundation for such a dynamic priority allocation, with which a processor capacity utilization of 100% can be achieved, can be found in the article entitled "Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment," in: Journal of the Association for Computing Machinery, vol. 20, January 1973, pp. 46-61. An algorithm for a priority allocation designated Earliest Deadline First (EDF) is therein described. According to EDF, of all the tasks awaiting processing, the one for which the time period for its processing expires the earliest receives the highest priority. In the article named, among other things there is also a comparison of the theoretical performance of a system having a static priority allocation with one having a dynamic priority allocation, and also a comparison of these systems with a mixed priority allocation.
Although with a dynamic priority allocation according to EDF a utilization of processor capacity of 100% can be achieved, the performance of the system is not improved, since the processor must additionally process the algorithm for the priority allocation. In practice, it has turned out that in some cases the algorithm for the priority allocation causes an overhead of up to 80% of the processor time, so that only 20% of the processor time is available for the actual processing of the tasks.
A reduction of the utilization of processor capacity by the processing of the priority allocation algorithm can be prevented by providing an additional processor for processing the priority allocation algorithm, the additional processor being exclusively responsible for this task. A solution variation of this type can be found in the article "Implementation and Evaluation of a Time-Driven Scheduling Processor," in: EEE Transactions on Computers, 7/88, p. 172ff.
With this system, it is possible to obtain 98% of the processor time for the processing of tasks. However, a solution of this type has the disadvantage that the hardware expense increases considerably, and the system is thus too expensive for many applications.